package com.example.algorithm.no0042.solution;

import com.example.algorithm.no0042.Solution;

/**
 * @author yumuhui <yumuhui@kuaishou.com>
 * Created on 2021-04-22
 * @Description 两数之和
 */
public class DoublePointSolutionImpl implements Solution {

    /**
     * {0,1,0,2,1,0,1,3,2,1,2,1}   6
     *
     * @param height {0,1,0,2,1,0,1,3,2,1,2,1}
     */
    @Override
    public int trap(int[] height) {

        if (height == null || height.length == 0) {
            return 0;
        }

        int length = height.length;
        int left = 0;
        int right = length - 1;
        int res = 0;
        int leftMax = 0;
        int rightMax = 0;

        while (right > left) {
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);

            if (leftMax < rightMax) {
                res += leftMax - height[left];
                left++;
            } else {
                res += rightMax - height[right];
                right--;
            }
        }

        return res;
    }
}
